package 前序非递归遍历;

import 相同的树.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
        //创建顺序表,存储前序遍历的序列
        List<Integer> ret = new ArrayList<>();
        //如果当前树是空树,直接返回空顺序表
        if (root == null){
            return ret;
        }
        //定义结点cur指向当前结点
        TreeNode cur = root;
        //创建栈stack,用来模拟递归效果
        Stack<TreeNode> stack = new Stack<>();
        //当栈不为空或者当前结点不为空,说明前序遍历没有完成
        while (!stack.empty() || cur != null){
            //当前结点不为空,说明当前结点的左子树没有遍历完成
            while (cur != null){
                //将当前结点入栈进行保存,等遍历当前结点右子树时可以弹出当前结点以寻找其右子树
                stack.push(cur);
                //根据前序遍历顺序,将根结点先存入顺序表
                ret.add(cur.val);
                //当前结点对左子树进行遍历
                cur = cur.left;
            }
            //左子树遍历完成,弹出栈顶元素对栈顶元素右子树进行遍历
            cur = stack.pop().right;
        }
        //将前序遍历序列存入顺序表中,返回顺序表地址ret
        return ret;
    }
}